package com.dragon.datastructure.sort;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @author dragon
 * @since 2019/12/25
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] array = {10, 2, 8, 1, 0, 5, 7, 9};
        mergeSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }


    public static void mergeSort(int[] array, int left, int right) {
        if (left == right) {
            return;
        } else {
            int middle = (left + right) >> 1;
            mergeSort(array, left, middle);
            mergeSort(array, middle + 1, right);
            merge(array, left, middle, right);
        }
    }

    /**
     * 合并两个有序的数组到一个数组里面去
     *
     * @param array  要合并的数组
     * @param left
     * @param middle
     * @param right
     */
    private static void merge(int[] array, int left, int middle, int right) {
        // 左边数组长度
        int left_size = middle - left + 1;
        // 右边数组长度
        int right_size = right - middle;
        int[] leftArray = new int[left_size];
        int[] rightArray = new int[right_size];
        // 填充左边数组元素
        for (int i = left; i <= middle; i++) {
            leftArray[i - left] = array[i];
        }
        // 填充右边数组元素
        for (int i = middle + 1; i <= right; i++) {
            rightArray[i - (middle + 1)] = array[i];
        }
        int i = 0;
        int j = 0;
        int k = left;
        while (i < left_size && j < left_size) {
            if (leftArray[i] < rightArray[j]) {
                array[k] = leftArray[i];
                i++;
            } else {
                array[k] = rightArray[j];
                j++;
            }
            k++;
        }
        while (i < left_size) {
            array[k++] = leftArray[i++];
        }

        while (j < right_size) {
            array[k++] = rightArray[j++];
        }
    }
}
